package jun;

import java.awt.*;
import java.util.Arrays;
import java.util.HashMap;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-15 14:25
 * @description：
 * @modified By：
 * @version:
 */
public class Jun15 {
    /**
     * 记忆化回溯（也称为递归+备忘录），自顶向下
     * 采用记忆化后的时间复杂度为O(2^n)(如果不进行记忆的话，时间复杂度将是O(n!))，可以理解为已经缩成了只有一个分支了
     * 然后为什么要进行记忆化：
     * 因为我们发现，例如[2,3]和[3,2]之后的玩家选择状态都是一样的，都是可以从除了2,3之外的
     * 数字进行选择，那么就可以对选择2和3后第一个玩家能不能赢进行记忆存储
     * 这里采用state[]数组存储每个数字是否都被选过，选过则记录为1，然后我们将state.toString()
     * 使得[2,3]和[3,2]它们的结果都是一样的"0011"，作为key，存储在HashMap中，value是选了2和3
     * 之后第一个玩家是否稳赢
     *
     * @param maxChoosableInteger
     * @param desiredTotal
     * @return
     */
    public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
            return false; //1,..maxChoosable数列总和都比目标和小
        int[] state = new int[maxChoosableInteger + 1];  //state[1]=1表示1被选了

        return backtraceWitMemo(state, desiredTotal, new HashMap<String, Boolean>());
    }

    private static boolean backtraceWitMemo(int[] state, int desiredTotal, HashMap<String, Boolean> map) {
        String key = Arrays.toString(state); //这里比较关键，如何表示这个唯一的状态，例如[2,3]和[3,2]都是"0011"，状态一样
        if (map.containsKey(key)) return map.get(key);  //如果已经记忆了这样下去的输赢结果,记忆是为了防止如[2,3]，[3,2]之后的[1,4,5,..]这个选择区间被重复计算

        for (int i = 1; i < state.length; i++) {
            if (state[i] == 0) { //如果这个数字i还没有被选中
                state[i] = 1;
                //如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了
                if (desiredTotal - i <= 0 || !backtraceWitMemo(state, desiredTotal - i, map)) {
                    map.put(key, true);
                    state[i] = 0; //在返回之前回溯
                    return true;
                }
                //如果不能赢也要记得回溯
                state[i] = 0;
            }
        }
        //如果都赢不了
        map.put(key, false);
        return false;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/linked-list-in-binary-tree/submissions/ 1367. 二叉树中的列表
     * create time: 2020-6-15 16:29
     * @params [head, root]
     * @return boolean
     */
    public boolean isSubPath(ListNode head, TreeNode root) {

        if(head == null) return true;
        if(root == null) return false;
        if (head.val == root.val) return isSubPathLoop(head.next, root.left) || isSubPathLoop(head.next, root.right)
                || isSubPath(head, root.left) || isSubPath(head, root.right);
        else return isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    private boolean isSubPathLoop(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        if (head.val == root.val)
            return isSubPathLoop(head.next, root.left) || isSubPathLoop(head.next, root.right);
        else
            return false;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum/solution/zuo-ti-guo-cheng-ji-lu-dpjie-fa-by-maverickbytes/ 1155. 掷骰子的N种方法
     * create time: 2020-6-15 16:29
     * @params [d, f, target]
     * @return int
     */
    private static final int MOD = 1000000007;
//    public int numRollsToTarget(int d, int f, int target) {
//        //i是丢i个骰子 他们的和为j 的方案数量为值
//        int[][] dp = new int[31][1001];
//        int min = Math.min(f, target);
//        for (int i = 1; i <= min; i++) {//把只丢一个骰子的方案全部初始化
//            dp[1][i] = 1;
//        }
//        int targetMax = d * f;//最大能到什么极限
//        for (int i = 2; i <= d; i++) {
//            for (int j = i; j <= targetMax; j++) {
//                for (int k = 1; j - k >= 0 && k <= f; k++) {
//                    //比如d=2 f=6 target = 10
//                    //现在i=2 j=8 dp[2][8] = dp[1][8-(1-f)]
//                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
//                }
//            }
//        }
//        //baseCase为0
//        return dp[d][target];
//    }
    public int numRollsToTarget(int d, int f, int target) {
        int[][] dp = new int[31][1001];
        int min = Math.min(f,target);
        for (int i = 1; i < min; i++) {
            dp[1][i] = 1;
        }
        int max = d*f;
        for (int i = 2; i <= d ; i++) {
            for (int j = i; j <= max; j++) {
                for (int k = 1;j-k>0 && k<=f ; k++) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
                }
            }
        }
        return dp[d][target];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/filling-bookcase-shelves/ 1105. 填充书架
     * create time: 2020-6-15 17:00
     * @params [books, shelf_width]
     * @return int
     */
    public int minHeightShelves(int[][] books, int shelf_width) {
        int num = books.length;
        if (num == 1) {
            return books[0][1];
        }
        int[] dp = new int[num];
        dp[0] = books[0][1];
        for (int i = 1; i < num; i++) {
            int height = books[i][1];
            int weight = books[i][0];
            dp[i] = dp[i - 1] + books[i][1];
            for (int j = i - 1; j >= 0; j--) {
                height = Math.max(height, books[j][1]);
                weight = weight + books[j][0];
                if (weight > shelf_width) {
                    break;
                }
                if (j == 0) {
                    dp[i] = Math.min(dp[i], height);
                } else {
                    dp[i] = Math.min(dp[i], dp[j - 1] + height);
                }

            }
        }
        return dp[num - 1];
    }

    public static void main(String[] args) {
        canIWin(10, 11);
    }
}


